﻿//day21-01 牛客：爱丽丝人偶，题号：1113894
//解法：贪心
//int main()
//{
//    int n = 0;
//    cin >> n;
//    int left = 1, right = n;
//    while (left < right)
//    {
//        cout << left << " " << right << " ";
//        left++;
//        right--;
//    }
//    if (left == right) cout << left;
//    return 0;
//}


//day21-02 牛客：集合，题号：105620
//解法：排序/set
//const int N = 1e4 + 10;
//int arr[2 * N];
//int n, m;
//
//int main()
//{
//    cin >> n >> m;
//    for (int i = 0; i < n + m; i++) cin >> arr[i];
//    sort(arr, arr + n + m);
//    cout << arr[0] << " ";
//    for (int i = 1; i < n + m; i++)
//    {
//        if (arr[i] != arr[i - 1]) cout << arr[i] << " ";
//    }
//
//    return 0;
//}


//day21-03 牛客：最⻓回⽂⼦序列，题号：2363349
//解法：区间dp
//const int N = 1e3 + 10;
//int dp[N][N];
//
////dp[i][j]表示：字符串[i,j]区间所有子序列中，最长回文子序列的长度
//int main()
//{
//    string s;
//    cin >> s;
//    int n = s.size();
//    s = " " + s;
//    for (int i = n + 1; i >= 1; i--)
//    {
//        for (int j = i; j <= n; j++)
//        {
//            if (i == j) dp[i][j] = 1;
//            else if (i + 1 == j && s[i] == s[j]) dp[i][j] = 2;
//            else
//            {
//                if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
//                else dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
//            }
//        }
//    }
//    cout << dp[1][n] << endl;
//    return 0;
//}